package com.chj.lintcode.backpack;

public class Code05_BackpackV {
	/**
	 * @param nums: an integer array and all positive numbers
	 * @param target: An integer
	 * @return: An integer
	 */
	public int backPackV(int[] nums, int target) {
		// write your code here
		int n = nums.length;
		int[][] dp = new int[n + 1][target + 1];
		dp[0][0] = 1;

		for (int i = 1; i <= target; i++) {
			dp[0][i] = 0;
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= target; j++) {
				dp[i][j] = dp[i - 1][j];
				if (j >= nums[i - 1]) {
					dp[i][j] += dp[i - 1][j - nums[i - 1]];
				}
			}
		}

		return dp[n][target];
	}
}
